package com.feiuxiu.datastructure.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * description: 实现动态数组
 * author: feixiu
 * date:2025/9/9 9:31
 */
public class MyArrayList<E> {
    //真正存储数据的底层数组
    private E[] data;
     //记录当前元素个数
    private  int size;
    //默认初始容量
    private static final int INIT_CAP=1;


    // 初始化
    public MyArrayList() {
        this(INIT_CAP);
    }
    public MyArrayList(int initCapacity) {
        data=(E[]) new Object[initCapacity];
        size=0;
    }
    //增

    public void addLast(E e){
        int cap=data.length;
        //看data数组容量够不够，不够就扩容
        if (size==cap){
            resize(2*cap);
        }
        //在尾部插入元素
        data[size]=e;
        size++;
    }

    public void add(int index,E e){
        checkPositionIndex(index);
        int cap=data.length;
        //看data数组容量够不够，不够就扩容
        if (size==cap){
            resize(2*cap);
        }
        // 版衣数据 data[index..] ->data[index+1..]
        // 给新元素腾出位置
        for (int i = size-1; i >=index; i--) {
            data[i+1]=data[i];
        }
        //插入新元素
        data[index]=e;
        size++;
    }

    public void addFirst(E e){
        add(0,e);
    }

    //删除
    public E removeLast(){
        if (size==0){
            throw new NoSuchElementException();
        }
        int cap= data.length;
        //可以缩容，节省空间
        if (size==cap/4){
            resize(cap/2);
        }
        E deleteVal=data[size-1];
        //把最后一个元素赋值为null，防止内存泄露
        data[size-1]=null;
        size--;
        return deleteVal;
    }
    public E remove(int index){
        //检查索引越界
        checkElementIndex(index);
        int cap= data.length;
        //可以缩容，节省空间
        if (size==cap/4){
            resize(cap/2);
        }
        E deleteVal=data[index];
        //搬移数据 data[index+1..] ->data[index..]
        for (int i=index;i<size-1;i++){
            data[i]=data[i+1];
        }

        //把最后一个元素赋值为null，防止内存泄露
        data[size-1]=null;
        size--;
        return deleteVal;
    }
    public E removeFirst(){
        return remove(0);
    }

    //查询
    public E get(int index){
        //检查索引越界
        checkElementIndex(index);
        return data[index];
    }

    //改
    public E set(int index,E element){//返回旧数据
        //检查索引越界
        checkElementIndex(index);
        E oldVal=data[index];
        data[index]=element;
        return oldVal;
    }


    //工具方法
    public  int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }


    //将data的容量改为newCap
    private void resize(int newCap){
        E[] temp=(E[]) new Object[newCap];
        for (int i = 0; i < size; i++) {
            temp[i]=data[i];
        }
        data=temp;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    //检查index 索引位置是否可以存在元素
    private void checkElementIndex(int index){
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: "+index +", Size: "+size);
    }
    //检查index 索引位置是否可以添加元素
    private void checkPositionIndex(int index){
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: "+index +", Size: "+size);
    }

    private void display(){
        System.out.println("Size: "+size +", cap: "+data.length);
        System.out.println(Arrays.toString(data));
    }

    public static void main(String[] args) {
        MyArrayList<Integer> arr = new MyArrayList<>(3);
        for (int i = 0; i < 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1,9);
        arr.addFirst(100);
        int val=arr.removeLast();
        arr.display();

    }

}
